Many garbage copying garbage collectors use short evacuation pauses to perform garbage collection (often using independently collectable regions to make the collection incremental). An example of a modern region-based incremental collector using stop-the-world evacuation pauses is illustrated in D. Detlefs et al: Garbage-First Garbage Collection, ISMM'04, pp. 37-48, ACM, 2004, which is hereby incorporated herein by reference.
In many applications it is desirable to obtain even shorter pause times, or to eliminate stop-the-world pauses altogether. F. Pizlo et al: STOPLESS: A Real-Time Garbage Collector for Multiprocessors, ISMM'07, pp. 159-172, ACM, 2007, which is hereby incorporated herein by reference, describes a garbage collector for real-time applications with very short pause times, implemented using soft synchronization and using wide objects for copying. It uses a read barrier to coordinate access to old and new copies of objects. Various other modern concurrent real-time garbage collectors are described in F. Pizlo et al: A Study of Concurrent Real-Time Garbage Collectors, PLDI'08, pp. 33-44, ACM, 2008, which is hereby incorporated herein by reference.
Various alternative approaches to copying objects in real-time collectors are presented in the following patent application publications, which are hereby incorporated herein by reference:
U.S. 2008/0281886 A1 (Petrank et al), Nov. 13, 2008, “Concurrent, lock-free object copying” describes, among other things, a relocating mechanism that moves an object by using a status field related to a data field, possibly in an interim (wide) object space, which is then copied to a to-space object.
U.S. 2009/0222494 A1 (Pizlo et al), Sep. 3, 2009, “Optimistic object relocation” describes, among other things, a technique wherein memory accesses are monitored for a write to an object [that is being relocated], and if a write is detected during relocation, the relocation fails and the memory at the destination address is deallocated; but if no write is detected, the relocation succeeds and the references are updated to point to the destination address. The aborted relocation may then be retried (to a newly allocated destination address).
U.S. 2009/0222634 A1 (Pizlo et al), Sep. 3, 2009, “Probabilistic object relocation” describes, among other things, a method of relocating objects where the object relocation may mark the words of the object during relocation with a relocation value to indicate transfer to the destination memory without locking the threads. The threads may be configured to check the value in the source memory during object access, and to access the corresponding word of the destination memory if the source memory word comprises the relocation value.
U.S. Pat. No. 6,671,707 (Hudson et al), Dec. 30, 2003 (Method for practical concurrent copying garbage collection offering minimal thread block times), which is hereby incorporated herein by reference, teaches a method for concurrent copying garbage collection offering minimal thread blocking times without the use of read barriers. In their method, mutators may access and modify both the old and new copy of a modified object simultaneously, and a special write barrier is used for propagating writes from one copy to the other. In at least one embodiment, they use an atomic compare-and-swap instruction for installing a forwarding pointer in a copied object. Their object copying operation (FIG. 4E) verifies copying of every word by reading back the written value and comparing it against the written value, and sometimes uses an atomic instruction for copying a word, which is a significant overhead over standard copying (a compare-and-swap instruction can cost up to about a hundred times the processing time and memory bandwidth of a normal pipelined burst-mode memory write). A related academic paper is R. Hudson and J. E. B. Moss: Sapphire: Copying GC Without Stopping the World, JAVA Grande/ISCOPE'01, pp. 48-57, ACM, 2001, which is hereby incorporated herein by reference.
The Hudson&Moss method has been further developed in T. Kalibera: Replicating Real-Time Garbage Collector for Java, JTRES'09, pp. 100-109, ACM, September 2009, which is hereby incorporated herein by reference.
A recent survey on reorganizing data structures, including a section related to garbage collection (especially as it relates to persistent object systems), is provided in G. Sockut et al: Online Reorganization of Databases, ACM Computing Surveys, 41(3), pp. 14:1-14:136, 2009, which is hereby incorporated herein by reference.
Surveys of distributed garbage collection algorithms can be found in S. Abdullahi et al: Garbage Collecting the Internet: A Survey of Distributed Garbage Collection, ACM Computing Surveys, 30(3):330-373, 1998 and S. Brunthaler: Distributed Garbage Collection Algorithms, Seminar Garbage Collection, Institute for System software, January 2006. The references contained therein provide extensive information on general implementation techniques for distributed garbage collection.
Distributed shared memory refers to systems where several computers that do not have hardware shared memory share a single address space accessible to software running on each of the nodes. In effect, it creates an illusion of a shared memory for application programs. Extensive research on distributed shared memory took place in the 1990's. Some references include:
M. Shapiro and P. Ferreira: Larchant-RDOSS: a Distributed Shared Persistent Memory and its Garbage Collector, WDAG'95 (9th International Workshop on Distributed Algorithms), pp. 198-214, Lecture Notes in Computer Science 972, Springer, 1995
J. Protic et al: A Survey of Distributed Shared Memory Systems, 28th Hawaii International Conference on System Sciences (HICSS'95), pp. 74-84, 1995
R. Kordale et al: Distributed/concurrent garbage collection in distributed shared memory systems, 3rd International Workshop on Object Orientation in Operating Systems, pp. 51-60, IEEE, 1993.
Distributed shared memory may allow migration or replication of objects to several nodes, and some distributed shared memory systems implement fine-grained synchronization of updates (frequently in connection with the implementation of distributed mutual exclusion algorithms and/or distributed memory barrier operations).
Known concurrent garbage collectors generally require using either a read barrier during object relocation, or verifying each word copy, or using atomic instructions for copying. Since reads are much more frequent in applications than writes, using a read barrier imposes a significant overhead on applications. Avoiding atomic instructions may yield significant performance improvements. Synchronization between a write barrier and a read barrier can also be very difficult to implement efficiently in a distributed environment.